package com.jsy.common.leetcode;

import io.swagger.models.auth.In;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import static org.jeecg.modules.jmreport.desreport.b.d.e;
import static org.jeecg.modules.jmreport.desreport.b.d.i;

public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        node1.left = node2;
        node1.right = node3;
        node1.right.left = node4;
//        System.out.println(solution.maxDepth(node1));
//        solution.buildTree2(new int[]{9,3,15,20,7},new int[]{9,15,7,20,3});
//        char[][] chars = {{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}};
//        solution.solve(chars);

//        int chars = new Solution2().minMutation("AGCAAAAA", "GACAAAAA", new String[]{"AGCAAAAA","GGTAAAAA","GATAAAAA","GACAAAAA"});
//        WordDictionary wordDictionary = new WordDictionary();
//        wordDictionary.addWord("bad");
//        wordDictionary.addWord("dad");
//        wordDictionary.addWord("mad");
//        boolean search = wordDictionary.search("bad");
//        boolean search = wordDictionary.search(".ad");
//        boolean search = wordDictionary.search("bad");
//        System.out.println(search);
//        List<String> words = new Solution2().findWords(new char[][]{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}}, new String[]{"oath", "pea", "eat", "rain"});
//        List<String> words = new Solution2().findWords(new char[][]{{'a','b'},{'c','d'}}, new String[]{"abcd"});
//        List<String> words = new Solution2().findWords(new char[][]{{'a','b','c'},{'a','e','d'},{'a','f','g'}}, new String[]{"abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"});
//        List<String> words = new Solution2().findWords(new char[][]{{'a','b','c'},{'a','e','d'},{'a','f','g'}}, new String[]{"abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"});
//        List<String> words = new Solution2().findWords2(new char[][]{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}}, new String[]{"oath", "pea", "eat", "rain"});
//        List<List<Integer>> list = new Solution2().combine(4, 2);
//        List<List<Integer>> list = new Solution2().permute(new int[]{1,2,3});
//        List<List<Integer>> list = new Solution2().combinationSum(new int[]{2,3,6,7}, 7);
//        List<List<Integer>> list = new Solution2().combinationSum(new int[]{3,2,5}, 8);
//        Integer list = new Solution2().totalNQueens(0);
//        Integer list = new Solution2().totalNQueens(1);
//        Integer list = new Solution2().totalNQueens(2);
//        Integer list = new Solution2().totalNQueens(3);
//        Integer list = new Solution2().totalNQueens(4);
//        Integer list = new Solution2().totalNQueens(5);
//        boolean list = new Solution2().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}, "SEE");
        TreeNode list = new Solution2().sortedArrayToBST(new int[]{1,2,3,4,5,6,7});
        System.out.println(list);

    }

    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return p!=null && q!=null ? p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right) : p==q;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        TreeNode leftNode = invertTree(root.left);
        TreeNode rightNode = invertTree(root.right);
        root.right = leftNode;
        root.left = rightNode;
        return root;
    }

    public boolean isSymmetric(TreeNode p, TreeNode q) {
        return p!=null && q!=null ? p.val == q.val && isSymmetric(p.left,q.right) && isSymmetric(p.right,q.left) : p==q;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }else if (root.left == null && root.right == null){
            return true;
        }else if (root.left == null || root.right == null){
            return false;
        }else {
            return isSymmetric(root.left,root.right);
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构建哈希映射
        Map<Integer, Integer> indexMap  = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i],i);
        }
        return buildMyTree(preorder,0,n-1,inorder,0,n-1,indexMap);
    }

    private TreeNode buildMyTree(int[] preorder, int preorder_left, int preorder_right, int[] inorder, int inorder_left, int inorder_right, Map<Integer, Integer> indexMap) {
        if (preorder_left > preorder_right){
            return null;
        }
        int preorder_root = preorder_left;
        int inorder_root = indexMap.get(preorder[preorder_root]);
        TreeNode root = new TreeNode(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;
        root.left = buildMyTree(preorder,preorder_left+1,preorder_left+size_left_subtree,inorder,inorder_left,inorder_root-1,indexMap);
        root.right = buildMyTree(preorder,preorder_left+size_left_subtree+1,preorder_right,inorder,inorder_root+1,inorder_right,indexMap);
        return root;
    }

    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        int n = postorder.length;
        // 构建哈希映射
        Map<Integer, Integer> indexMap  = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i],i);
        }
        return buildMyTree2(postorder,0,n-1,inorder,0,n-1,indexMap);
    }

    private TreeNode buildMyTree2(int[] postorder, int postorder_left, int postorder_right, int[] inorder, int inorder_left, int inorder_right, Map<Integer, Integer> indexMap) {
        if (postorder_left > postorder_right){
            return null;
        }
        int preorder_root = postorder_right;
        System.out.println(postorder[preorder_root]);
        int inorder_root = indexMap.get(postorder[preorder_root]);
        TreeNode root = new TreeNode(postorder[preorder_root]);
        int size_right_subtree = inorder_right - inorder_root;
        root.right = buildMyTree2(postorder,postorder_right - size_right_subtree,postorder_right-1,inorder,inorder_root+1,inorder_right,indexMap);
        root.left = buildMyTree2(postorder,postorder_left,postorder_right - size_right_subtree-1,inorder,inorder_left,inorder_root-1,indexMap);
        return root;
    }

    public Node2 connect(Node2 root) {
        if (root == null) {
            return null;
        }
        Queue<Node2> queue = new ArrayDeque<Node2>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
                Node2 node = queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
                node.next = size==1 ? null : queue.peek();
                size--;
            }
        }
        return root;
    }

    public void flatten(TreeNode root) {
        List<TreeNode> treeNodes = new ArrayList<>();
        if (root == null){
            return;
        }
        addNode(root,treeNodes);
        for (int i = 0; i < treeNodes.size(); i++) {
            TreeNode node = treeNodes.get(i);
            node.left = null;
            node.right = i== treeNodes.size()-1 ? null : treeNodes.get(i+1);
        }
    }

    private void addNode(TreeNode root, List<TreeNode> treeNodes) {
        if (root != null){
            treeNodes.add(root);
            addNode(root.left,treeNodes);
            addNode(root.right,treeNodes);
        }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null){
            return false;
        }
        if (root.left == null && root.right == null){
            return root.val == targetSum;
        }
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum- root.val);
    }

    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }

    private int dfs(TreeNode root, int sum) {
        if (root == null){
            return 0;
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null){
            return sum;
        }else {
            return dfs(root.left,sum) +  dfs(root.right,sum);
        }
    }

    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int maxSum = Integer.MIN_VALUE;
        gainSum(root);
        return maxSum;
    }

    public int gainSum(TreeNode root) {
        if (root == null){
            return 0;
        } else {
            int left = Math.max(gainSum(root.left), 0);
            int right = Math.max(gainSum(root.right),0);
            maxSum = Math.max(maxSum,root.val + left + right);
            return root.val + Math.max(left,right);
        }
    }

    public int numIslands(char[][] grid) {
        int islands  = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1'){
                    islands++;
                    dfs(grid,r,c);
                }
            }
        }
        return islands;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0'){
            return;
        }
        grid[r][c] = '0';
        dfs(grid,r+1,c);
        dfs(grid,r-1,c);
        dfs(grid,r,c-1);
        dfs(grid,r,c+1);
    }

    private int[][] dirs = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    private int[] ints = new int[2];

    public void solve(char[][] board) {
        int length = board.length;
        int width = board[0].length;
        for (int i = 0; i < width; i++) {
            dfsSolve(board,0,i);
            dfsSolve(board,length-1,i);
        }
        for (int i = 0; i < length; i++) {
            dfsSolve(board,i,0);
            dfsSolve(board,i,width-1);
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] == 'A'){
                  board[i][j] = 'O';
                }else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfsSolve(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == 'A' || grid[r][c] == 'X'){
            return;
        }
        grid[r][c] = 'A';
        dfsSolve(grid,r+1,c);
        dfsSolve(grid,r-1,c);
        dfsSolve(grid,r,c-1);
        dfsSolve(grid,r,c+1);
    }

    public GraphNode cloneGraph(GraphNode node) {
        HashMap<GraphNode, GraphNode> graphMap = new HashMap<>();
        GraphNode graphNodeRoot = new GraphNode();
        GraphNode current = graphNodeRoot;
        GraphNode origin = node;
        System.out.println(node);
        return cloneGraph(current,graphMap,origin);
    }

    private GraphNode cloneGraph(GraphNode current, HashMap<GraphNode, GraphNode> graphMap, GraphNode origin) {
        if (origin == null){
            return current;
        }
        if (!graphMap.containsKey(origin)){
            GraphNode neighbor = new GraphNode(origin.val,new ArrayList<>());
            graphMap.put(origin,current);
            for (GraphNode graphNode : origin.neighbors) {
                neighbor.neighbors.add(cloneGraph(neighbor,graphMap,graphNode));
            }
            return current;
        }else {
            GraphNode graphNode = graphMap.get(origin);
            return graphNode;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationsSize = equations.size();
        UnionFind unionFind = new UnionFind(2 * equationsSize);
        Map<String,Integer> hashMap = new HashMap<>(2*equationsSize);
        int id = 0;
        for(int i=0; i<equationsSize;i++){
            List<String> equation = equations.get(i);
            String var1 = equation.get(0);
            String var2 = equation.get(1);
            if(!hashMap.containsKey(var1)){
                hashMap.put(var1,id);
                id++;
            }
            if(!hashMap.containsKey(var2)){
                hashMap.put(var2,id);
                id++;
            }
            unionFind.union(hashMap.get(var1),hashMap.get(var2),values[i]);
        }

        int queriesSize = queries.size();
        double[] res = new double[queriesSize];
        for(int i=0;i<queriesSize;i++){
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);
            Integer id1 = hashMap.get(var1);
            Integer id2 = hashMap.get(var2);
            if(id1 == null || id2 == null){
                res[i] = -1.0d;
            }else{
                res[i] = unionFind.isConnected(id1,id2);
            }
        }
        return res;
    }
    /**
     * 并查集
     */
    private class UnionFind{
        private int[] parent;
        private double[] weight;
        public UnionFind(int n){
            this.parent = new int[n];
            this.weight = new double[n];
            for(int i= 0;i<n;i++){
                parent[i] = i;
                weight[i] = 1.0d;
            }
        }
        public void union(int x, int y, double value){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return;
            }
            parent[rootX] = rootY;
            weight[rootX] = weight[y] * value/weight[x];
        }

        public int find(int x){
            if(x!=parent[x]){
                int origin = parent[x];
                parent[x] = find(parent[x]);
                weight[x] *= weight[origin];
            }
            return parent[x];
        }

        public double isConnected(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return weight[x] /weight[y];
            }else {
                return -1.0d;
            }
        }
    }

    List<List<Integer>> edges;
    int [] visited;
    boolean valid = true;
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
      edges = new ArrayList<List<Integer>>();
      for (int i = 0; i < numCourses; ++i) {
        edges.add(new ArrayList<Integer>());
      }
      visited = new int[numCourses];
      for (int[] info : prerequisites) {
        edges.get(info[1]).add(info[0]);
      }
      for (int i = 0; i < numCourses && valid; ++i) {
        if (visited[i] == 0) {
          dfs(i);
        }
      }
      return valid;
    }

    public void dfs(int u) {
        visited[u] = 1;
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    int [] indeg;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges =  new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }
        int visited = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            visited++;
            for (int v: edges.get(u)) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return visited == numCourses;
    }


    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[] vis = new boolean[n * n + 1];
        queue.offer(new int[]{1, 0});
        while (!queue.isEmpty()){
            int[] p = queue.poll();
            for (int i = 1; i <= 6; i++) {
                int nxt = p[0] + i;
                if (nxt > n * n){ // 超出边界
                    break;
                }
                int [] rc = id2rc(nxt,n); // 得到下一步的行列
                if (board[rc[0]][rc[1]] != -1){ // 存在蛇或梯子
                    nxt = board[rc[0]][rc[1]];
                }
                if (nxt == n * n){ // 到达终点
                    return p[1] + 1;
                }
                if (!vis[nxt]){
                    vis[nxt] = true;
                    queue.offer(new int[]{nxt, p[1] + 1}); // 扩展新状态
                }
            }
        }
        return -1;
    }
    private int[] id2rc(int id, int n){
        int r = (id - 1) / n;
        int c = (id - 1) % n;
        if (r % 2 == 1){
            c = n - 1 - c;
        }
        r = n - 1 - r;
        return new int[]{r,c};
    }

    public int minMutation(String startGene, String endGene, String[] bank) {
        int length = startGene.length();
        HashSet<String> bankSet = new HashSet<>();
        HashSet<String> visit = new HashSet<>();
        for (String s : bank) {
            bankSet.add(s);
        }
        if (startGene.equals(endGene)) {
            return 0;
        }
        if (!bankSet.contains(endGene)) {
            return -1;
        }
        char[] chars = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        visit.add(startGene);
        int step = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                String current = queue.poll();
                for (int i = 0; i < length; i++) {
                    for (int j = 0; j < 4; j++) {
                        if (current.charAt(i) != chars[j]){
                            StringBuilder sb = new StringBuilder(current);
                            sb.setCharAt(i, chars[j]);
                            String next = sb.toString();
                            if (!visit.contains(next) && bankSet.contains(next)){
                                if (next.equals(endGene)){
                                    return step;
                                }
                                queue.offer(next);
                                visit.add(next);
                            }
                        }
                    }
                }
                size--;
            }
            step ++;
        }
        return -1;
    }

    /**
     * 递归回溯法
     */
    int ans = Integer.MAX_VALUE;
    public int minMutation2(String start, String end, String[] bank) {
        backtrack(start, end, bank, new boolean[bank.length], 0);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public void backtrack(String start, String end, String[] bank, boolean[] used, int t) {
        if (t >= ans) return;
        if (start.equals(end)) {
            ans = Math.min(ans, t);
        } else {
            for (int i = 0, diff = 0; i < bank.length; i++, diff = 0) {
                if (used[i]) continue;
                for (int j = 0; j < start.length(); j++)
                    diff += start.charAt(j) != bank[i].charAt(j) ? 1 : 0;
                if (diff == 1) {
                    used[i] = true;
                    backtrack(bank[i], end, bank, used, t + 1);
                    used[i] = false;
                }
            }
        }
    }


    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        backtrack(beginWord, endWord, wordList, new boolean[wordList.size()], 0);
        return ans == Integer.MAX_VALUE ? 0 : ans+1;
    }
 public int ladderLength2(String beginWord, String endWord, List<String> wordList) {
     int length = beginWord.length();
     HashSet<String> bankSet = new HashSet<>();
     HashSet<String> visit = new HashSet<>();
     for (String s : wordList) {
         bankSet.add(s);
     }
     if (beginWord.equals(endWord)) {
         return 0;
     }
     if (!bankSet.contains(endWord)) {
         return 0;
     }
     char[] chars = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
     Queue<String> queue = new LinkedList<>();
     queue.offer(beginWord);
     visit.add(beginWord);
     int step = 1;
     while (!queue.isEmpty()){
         int size = queue.size();
         while (size > 0){
             String current = queue.poll();
             for (int i = 0; i < length; i++) {
                 for (int j = 0; j < chars.length; j++) {
                     if (current.charAt(i) != chars[j]){
                         StringBuilder sb = new StringBuilder(current);
                         sb.setCharAt(i, chars[j]);
                         String next = sb.toString();
                         if (!visit.contains(next) && bankSet.contains(next)){
                             if (next.equals(endWord)){
                                 return step+1;
                             }
                             queue.offer(next);
                             visit.add(next);
                         }
                     }
                 }
             }
             size--;
         }
         step ++;
     }
     return 0;
    }

    public void backtrack(String start, String end, List<String> bank, boolean[] used, int t) {
        if (t >= ans) return;
        if (start.equals(end)) {
            ans = Math.min(ans, t);
        } else {
            for (int i = 0, diff = 0; i < bank.size(); i++, diff = 0) {
                if (used[i]) continue;
                for (int j = 0; j < start.length(); j++)
                    diff += start.charAt(j) != bank.get(i).charAt(j) ? 1 : 0;
                if (diff == 1) {
                    used[i] = true;
                    backtrack(bank.get(i), end, bank, used, t + 1);
                    used[i] = false;
                }
            }
        }
    }

    public int[] rowAndMaximumOnes(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int index = 0;
        int max = 0;
        for(int i = 0 ;i < m;i++){
            int count = 0;
            for(int j = 0 ;j <n;i++){
                if(mat[i][j]==1){
                    count++;
                }
            }
            if(count>max){
                index = i;
                max = count;
            }
        }
        return new int[]{index,max};
    }


    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (findWord(board, word)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean findWord(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)){
                    if (dfs(board, i, j,word,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] grid, int r, int c, String word, int index) {
        if (index == word.length()){
            return true;
        }
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '-'){
            return false;
        }
        if (grid[r][c] != word.charAt(index)){
            return false;
        }
        grid[r][c] = '-';
        index++;
        boolean res = dfs(grid,r+1,c,word,index) || dfs(grid,r-1,c,word,index) || dfs(grid,r,c-1,word,index) || dfs(grid,r,c+1,word,index);
        grid[r][c] = word.charAt(index-1);
        return res;
    }

    private boolean dfs(char[][] grid, int r, int c, Trie now,Set<String> ans) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '-'){
            return false;
        }
        if (!now.children.containsKey(grid[r][c])){
            return false;
        }
        now = now.children.get(grid[r][c]);
        if (now.word != null){
            ans.add(now.word);
        }
        char before = grid[r][c];
        grid[r][c] = '-';
        boolean res = dfs(grid,r+1,c,now,ans) || dfs(grid,r-1,c,now,ans) || dfs(grid,r,c-1,now,ans) || dfs(grid,r,c+1,now,ans);
        grid[r][c] = before;
        return res;
    }
    public List<String> findWords2(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            trie.insert(words[i]);
        }
        Set<String> ans = new HashSet<String>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, trie, ans);
            }
        }
        return new ArrayList<>(ans);
    }
    public List<String> letterCombinations(String digits) {
        Map<Character, String[]> digitMap = new HashMap<>();
        digitMap.put('2', new String[]{"a", "b", "c"});
        digitMap.put('3', new String[]{"d", "e", "f"});
        digitMap.put('4', new String[]{"g", "h", "i"});
        digitMap.put('5', new String[]{"j", "k", "l"});
        digitMap.put('6', new String[]{"m", "n", "o"});
        digitMap.put('7', new String[]{"p", "q", "r", "s"});
        digitMap.put('8', new String[]{"t", "u", "v"});
        digitMap.put('9', new String[]{"w", "x", "y", "z"});
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) {
            return ans;
        }
        dfs(ans, new StringBuilder(), digits, 0,digitMap);
        return ans;
    }

    private void dfs(List<String> ans, StringBuilder sb, String digits, int index, Map<Character, String[]> digitMap) {
        if (index == digits.length()) {
            ans.add(sb.toString());
            return;
        }
        char c = digits.charAt(index++);
        for (String s : digitMap.get(c)) {
            sb.append(s);
            dfs(ans, sb, digits, index, digitMap);
            sb = sb.deleteCharAt(sb.length() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
//        List<List<Integer>> ans = new ArrayList<>();
        List<List<Integer>> ans = new LinkedList<>();
        combine(1, n, k, new LinkedList<>(), ans);
        return ans;
    }

    private void combine(int start, int n, int k, LinkedList<Integer> cur, List<List<Integer>> ans) {
        if (cur.size() + (n - start + 1) < k) {
            return;
        }
        if (k == cur.size()) {
//            ans.add(new ArrayList<>(cur));
            ans.add(new LinkedList<>(cur));
            return;
        }
        for (int i = start; i <= n; i++) {
            cur.add(i);
            combine(i+1, n, k, cur, ans);
            cur.removeLast();
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visit = new boolean[nums.length];
        permute(new ArrayList<Integer>(),0, nums, ans, visit);
        return ans;
    }

    private void permute(List<Integer> cur, int index, int[] nums, List<List<Integer>> ans, boolean[] visit) {
        if (index == nums.length){
            ans.add(new ArrayList<>(cur));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visit[i]){
                continue;
            }
            cur.add(nums[i]);
            visit[i] = true;
            permute(cur, index+1, nums, ans,visit);
            cur.remove(cur.size()-1);
            visit[i] = false;
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        combinationSum(candidates, target, new ArrayList<Integer>(), ans);
        return ans;
    }

    private void combinationSum(int[] candidates, int target, List<Integer> cur, List<List<Integer>> ans) {
        if (target == 0){
            ans.add(new ArrayList<>(cur));
        }else if (target < 0){
            return;
        }else {
            for (int i = 0; i < candidates.length; i++) {
                if (candidates[i] > target){
                    continue;
                }
                if (cur.size()> 0 && candidates[i] < cur.get(cur.size()-1)){
                    continue;
                }
                cur.add(candidates[i]);
                combinationSum(candidates, target-candidates[i], cur, ans);
                cur.remove(cur.size()-1);
            }
        }
    }


    public int totalNQueens(int n) {
        Set<Integer> row = new HashSet<>();
        Set<Integer> column = new HashSet<>();
        Set<Integer> diagonal = new HashSet<>();
        List<int[]> list = new ArrayList<>();
        List<List<int[]>> ans = new ArrayList<>();
        totalNQueens(n, 0,  row,column,diagonal,list,ans);
        return ans.size();
    }

    private void totalNQueens(int n, int i, Set<Integer> column, Set<Integer> diagonal1, Set<Integer> diagonal2, List<int[]> list, List<List<int[]>> ans) {
        if (i == n){
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int k = 0; k < n; k++) {
            if (column.contains(k) || diagonal2.contains(i+k) || diagonal1.contains(i-k)){
                continue;
            }
            list.add(new int[]{i,k});
            column.add(k);
            diagonal1.add(i-k);
            diagonal2.add(i+k);
            totalNQueens(n, i+1, column, diagonal1, diagonal2, list, ans);
            column.remove(k);
            diagonal1.remove(i-k);
            diagonal2.remove(i+k);
            list.remove(list.size()-1);
        }
    }

    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)){
                    if (dfs(board, i, j, word, 0)){
                        return true;
                    };
                }
            }
        }
        return false;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length-1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left>right){
            return null;
        }
        int mid = (left+right)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, left, mid-1);
        node.right = sortedArrayToBST(nums, mid+1, right);
        return node;
    }

    public ListNode sortList(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode root = head;
        while (root != null){
            list.add(root.val);
            root = root.next;
        }
        Collections.sort(list);
        root = head;
        for (int i = 0; i < list.size(); i++) {
            root.val = list.get(i);
            root = root.next;
        }
        return head;
    }

    public ListNode sortList2(ListNode head) {
        return sortList2(head, null);
    }

    private ListNode sortList2(ListNode head, ListNode tail) {
        if (head == null){
            return head;
        }
        if (head.next == tail){
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail){
            slow = slow.next;
            fast = fast.next;
            if (fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode left = sortList2(head, mid);
        ListNode right = sortList2(mid, tail);
        return  mergeTowList(left, right);
    }

    private ListNode mergeTowList(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode  dummyHead = dummy;
        while (left != null && right != null){
            if (left.val<=right.val){
                dummyHead.next = left;
                left = left.next;
            }else{
                dummyHead.next = right;
                right = right.next;
            }
            dummyHead = dummyHead.next;
        }
        if (left == null){
            dummyHead.next = right;
        }else{
            dummyHead.next = left;
        }
        return dummy.next;
    }

}